package com.yin.myproject.arithmetic;

import java.util.Arrays;

/**
 * @author Eason
 * @create 2018-04-29 20:54
 **/
public class Demo {
    public static void main(String[] args) {
        int array[] = {94, 12, 34, 76, 26, 9, 0, 37, 55, 76, 37, 5, 68, 83, 90, 37, 12, 65, 76, 49};
        Demo demo = new Demo();
        demo.quickSort(array);
    }

    private void mergesort(int[] array, int[] tempArray, int left, int right) {
        if (left < right) {
            int center = (left + right) / 2;
            mergesort(array, tempArray, left, center);
            mergesort(array, tempArray, center + 1, right);
            merge(array, tempArray, left, center, right);
        }
        return;
    }

    private int[] merge(int[] array, int[] tempArray, int left, int center, int right) {
        System.out.println("排序区间" + left + " - " + right);
        int i = left;
        int j = center + 1;
        int k = 0;
        while (i <= center && j <= right) {
            if (array[i] > array[j]) {
                tempArray[k++] = array[j++];
            } else {
                tempArray[k++] = array[i++];
            }
        }

        while (i <= center) {
            tempArray[k++] = array[i++];
        }
        while (j <= right) {
            tempArray[k++] = array[j++];
        }
        //拷贝临时数组的值到数组
        for (k = 0, i = left; i <= right; ) {
            array[i++] = tempArray[k++];
        }
        System.out.println("排序后的数组:" + Arrays.toString(array));
        return array;
    }

    private void mergesort(int[] array) {
        int temp[] = new int[array.length];
        mergesort(array, temp, 0, array.length - 1);
        System.out.println(Arrays.toString(array));
    }

    /**
     * 快速排序
     *
     * @param array
     */
    public void quickSort(int[] array) {
        quickSort(array, 0, array.length - 1);
    }

    /**
     * 快速排序
     *
     * @param array
     * @param low
     * @param high
     */
    private int[] quickSort(int[] array, int low, int high) {
        System.out.println("原数组:" + Arrays.toString(array));
        if (low < high) {
            int pivotPos = partion(array, low, high);
            System.out.println("返回的基准坐标:" + pivotPos);
            quickSort(array, 0, pivotPos);
            quickSort(array, pivotPos + 1, high);
        }
        return array;
    }

    /**
     * 快速排序 求基数坐标
     *
     * @param array
     * @param low
     * @param high
     * @return
     */
    private int partion(int[] array, int low, int high) {
        int pivot = (array[low] + array[high]) >> 1;
        while (low < high) {
            //左侧指针移动
            while (low < high && array[low] > pivot) {
                low++;
            }
            //右侧指针移动
            while (high > low && array[high] < pivot) {
                high--;
            }
            //左侧小于pivot的元素右移
            if (high > low) {
                int temp = array[low];
                array[low] = array[high];
                array[high] = temp;
                low++;
                high--;
            }
            continue;
        }
        System.out.println("排序后的数组:" + Arrays.toString(array));

        return low - 1;
    }
}
